package net.j4love.algorithm.chapter1;


import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * @author he peng
 * @create 2017/10/18 16:15
 * @see
 */
public class Train {


    /**
     * 双调查找。如果一个数组中的元素先递增后递减，则称这个数组为双调的。给定一个含有
     * N 个不同 int 值的双调数组 ，判断它是否含有给定的整数 。程序在最坏情况下所需的
     * 比较次数为 ~3logN
     * @throws Exception
     */
    @Test
    public void doubleBinarySearch_2() throws Exception {
        int[] source = {1,2,3,4,33,45,53,654,777,555,54,50,49,31,22,-1,-18,-26};
        Random random = new Random();
        int rn = 6;
        boolean exist = false;
        int targetIndex = -1;
        int tailIndex = source.length - 1;
        // TODO 还没实现
    }

    /**
     * 双调查找。如果一个数组中的元素先递增后递减，则称这个数组为双调的。给定一个含有
     * N 个不同 int 值的双调数组 ，判断它是否含有给定的整数 。线性级别
     * @throws Exception
     */
    @Test
    public void doubleBinarySearch_1() throws Exception {
        int[] source = {1,2,3,4,33,45,53,654,777,555,54,50,49,31,22,-1,-18,-26};
        int rn = 22;
        long st = System.currentTimeMillis();
        boolean exist = false;
        for (int i = 0 ; i < source.length ; i++ ) {
            if (rn == source[i]) {
                exist = true;
            }
        }
        long ot = System.currentTimeMillis();
        System.out.println("exist = " + exist + " , time = " + (ot - st) + " ms");
    }

    /**
     * 矩阵的局部最小元素。给定一个含有 N 平方个不同整数的 N*N 数组。
     * 设计一个运行时间和 N 成正比的算法来找出一个局部最小元素 ：满足
     * a[i][j] < a[i + 1][j] , a[i][j] < a[i][j + 1] ,
     * a[i][j] < a[i - 1][j] 以及 a[i][j] < a[i][j - 1] 的索引 i 和 j ，
     * 最坏情况下时间开销应该和N成正比
     *
     * @throws Exception
     */
    @Test
    public void matrixLocalMin_1() throws Exception {
        int[][] source = {
                {5,6,3,12,33},
                {4,1,2,-5,32},
                {7,8,9,-4,76},
                {17,18,-19,110,176},
                {27,38,29,666,716},
        };
        long st = System.currentTimeMillis();
        int n = source.length;
        int localMinRow = -1 , localMinColumn = -1 , rowOffset = 0 , columnOffset = 0;
        while (n > 2) {
            int row = source.length / 2 + rowOffset;
            int column = source.length / 2 + columnOffset;
            int val = source[row][column];
            boolean isFound = (val < source[row + 1][column]) && (val < source[row][column + 1])
                    && (val < source[row - 1][column]) && (val < source[row][column - 1]);
            if (isFound) {
                localMinRow = row;
                localMinColumn = column;
                break;
            }

            // 计算行、列偏移量
            if ((val > source[row - 1][column]) && (val > source[row + 1][column])) {
                if (source[row - 1][column] > source[row + 1][column]) {
                    rowOffset = -1;
                } else {
                    rowOffset = 1;
                }
            } else if (val > source[row - 1][column]) {
                rowOffset = -1;
            } else if (val > source[row + 1][column]) {
                rowOffset = 1;
            }

            if ((val > source[row][column - 1]) && (val > source[row][column + 1])) {
                if (source[row][column - 1] > source[row][column + 1]) {
                    columnOffset = 1;
                } else {
                    columnOffset = -1;
                }
            } else if (val > source[row][column - 1]) {
                columnOffset = -1;
            } else if (val > source[row][column + 1]) {
                columnOffset = 1;
            }

            // 计算新矩阵规模
            n -= row;
        }
        long ot = System.currentTimeMillis();
        System.out.println("local min row index = " + localMinRow +
                " , local min column index = " + localMinColumn + " , time = " + (ot - st) + " ms");
    }

    /**
     * 数组的局部最小元素 。给定一个含有 N 个不同整数的数组 ，
     * 找到一个局部最小元素：满足 a[i]<a[i - 1] 且 a[i]<a[i + 1]
     * 的索引 i 。最坏情况下的比较次数为 ~ 2logN
     * @throws Exception
     */
    @Test
    public void arrayLocalMin_2() throws Exception {
//        int[] source = {1,3,9,6,8,4};
        int n = 10000000;
        Random random = new Random();
        Set<Integer> set = new HashSet<>(n);
        while (set.size() < n) {
            set.add(random.nextInt());
        }
        Integer[] source = new Integer[n];
        source = set.toArray(source);
        long st = System.currentTimeMillis();
        int index = -1;
        // 算法思路 ： 检查数组的中间值 a[n/2] , a[n/2 - 1] ,a[n/2 + 1]
        // 如果满足条件程序终止 ， 否则在较小的相邻元素半边开始查找
        if (source[n / 2] < source[n / 2 - 1] && source[n / 2] < source[n / 2 + 1]) {
            index = n / 2;
        }
        if (-1 == index) {
            int i = source[n / 2 - 1] < source[n / 2 + 1] ? 0 : n / 2 + 1;
            if (i == 0) {
                for (; i < n / 2; i++ ) {
                    if (i == 0) {
                        continue;
                    }
                    if (source[i] < source[i - 1] && source[i] < source[i + 1]) {
                        index = i;
                    }
                }
            } else {
                for (; i < source.length; i++ ) {
                    if (i == source.length - 1) {
                        break;
                    }
                    if (source[i] < source[i - 1] && source[i] < source[i + 1]) {
                        index = i;
                    }
                }
            }
        }
        long ot = System.currentTimeMillis();
        System.out.println("index = " +  index + " , time = " + (ot - st) + " ms");
    }

    /**
     * 数组的局部最小元素 。给定一个含有 N 个不同整数的数组 ，
     * 找到一个局部最小元素：满足 a[i]<a[i - 1] 且 a[i]<a[i + 1]
     * 的索引 i 。线性级别算法
     * @throws Exception
     */
    @Test
    public void arrayLocalMin_1() throws Exception {

//        int[] source = {1,3,9,6,8,4};
        int n = 10000000;
        Random random = new Random();
        Set<Integer> set = new HashSet<>(n);
        while (set.size() < n) {
            set.add(random.nextInt());
        }
        Integer[] source = new Integer[n];
        source = set.toArray(source);
        int index = -1;
        long st = System.currentTimeMillis();
        for (int i = 0 ; i < source.length ; i++ ) {
            if (i == 0 || i == source.length - 1) {
                continue;
            }
            if (source[i] < source[i - 1] && source[i] < source[i + 1]) {
                index = i;
            }
        }
        long ot = System.currentTimeMillis();
        System.out.println("index = " +  index + " , time = " + (ot - st) + " ms");
    }


    /**
     * 最遥远的一对 ， 给定一个含有 N 个 double 值的数组，在其中找到一对最遥远的值：
     * 两者之差（绝对值）最大的两个数。线性级别的算法
     * @throws Exception
     */
    @Test
    public void maxDiffer() throws Exception {

        // 线性级别的算法 , 问题规模 N = 100000000 ， 时间开销约为 85 ms
//        double[] source = {2.3,2.28,3.43,1.01,-9.8,6.63,-3.04,2.2,0.2,-2.2};
        int n = 100000000;
        double[] source = new double[n];
        for (int i = 0 ; i < n ; i++ ) {
            source[i] =  Math.random();
        }
        long st = System.currentTimeMillis();
        double max = source[0];
        double min = source[0];
        for (int i = 0 ; i < source.length ; i++ ) {
            if (source[i] > max) {
                max = source[i];
            }
            if (source[i] < min) {
                min = source[i];
            }
        }
        long ot = System.currentTimeMillis();
        System.out.println("val-1 = " + max + " , val-2 = " + min + " , d-val = " + (max - min) + " , time = " + (ot - st) + " ms");

    }

    /**
     * 找到最接近的一对。给定一个含有 N 个 double 值的数组，在其中找到一对最接近的值：
     * 两者之差（绝对值）最小的两个数。线性对数级别算法
     * @throws Exception
     */
    @Test
    public void closest_2() throws Exception {

        // 线性对数级别算法 , 当问题规模 N 不断增大时,运行开销的时间没有显著增长 ，
        // N = 100000 时，时间开销大约为 24 ms ， 提升一个数量级 N = 1000000 时
        // 时间开销大约为 115 ms ， 当 N = 100000000 时 ，时间开销为 10969 ms
        // 大致和平方级别的算法在问题规模为 100000 时的时间开销相当

//        double[] source = {2.3,2.28,3.43,1.01,-9.8,6.63,-3.04,2.2,0.2,-2.2};
        int n = 100000000;
        double[] source = new double[n];
        for (int i = 0 ; i < n ; i++ ) {
            source[i] =  Math.random();
        }
        long st = System.currentTimeMillis();
        // 算法思路 ， 先排序 ， 排序之后两两相减
        Arrays.sort(source);
        Double v = null , val_1 = null, val_2 = null;
        for (int i = 0 ; i < source.length ; i++ ) {
            if (null == v) {
                val_1 = source[i];
                val_2 = source[i + 1];
                v = Math.abs(val_1 - val_2);
            }
            if (i + 1 == source.length) {
                break;
            }
            double abs = Math.abs(source[i] - source[i + 1]);
            if (v > abs) {
                v = abs;
                val_1 = source[i];
                val_2 = source[i + 1];
            }
        }
        long ot = System.currentTimeMillis();
        System.out.println("val-1 = " + val_1 + " , val-2 = " + val_2 + " , d-val = " + v + " , time = " + (ot - st) + " ms");
    }

    /**
     * 找到最接近的一对。给定一个含有 N 个 double 值的数组，在其中找到一对最接近的值：
     * 两者之差（绝对值）最小的两个数。平方级别的算法
     * @throws Exception
     */
    @Test
    public void closest_1() throws Exception {

        // 平方级别的算法在问题规模变大时运行时间越来越长 , N = 100000 时时间开销大约为 10253 ms
//        double[] source = {2.3,3.43,1.01,-9.8,6.63,-3.04,2.2};
        int n = 100000;
        double[] source = new double[n];
        for (int i = 0 ; i < n ; i++ ) {
            source[i] =  Math.random();
        }
        long st = System.currentTimeMillis();
        Double v = null , val_1 = null , val_2 = null;
        for (int i = 0 ; i < source.length ; i++ ) {
            double b = source[i];
            for (int j = i + 1 ; j < source.length ; j++ ) {
                double a = source[j];
                if (null == v) {
                    val_1 = b;
                    val_2 = a;
                    v = Math.abs(b-a);
                    continue;
                }
                double abs = Math.abs(b - a);
//                System.out.println("v = " + v + " , abs = " + abs);
                if (v > abs) {
                    val_1 = b;
                    val_2 = a;
                    v = abs;
                }
            }
        }
        long ot = System.currentTimeMillis();
        System.out.println("val-1 = " + val_1 + " , val-2 = " + val_2 + " , d-val = " + v + " , time = " + (ot - st) + " ms");

    }
}
